In [ ]:
#!/usr/bin/python
#-*- coding: UTF-8 -*-
kNN分类算法¶
计算测试点到已标记数据集各点的距离，
选择距离最近的k个已标记点进行举手表决，
以出现频次最高的标记作为测试点的预测标记
优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型、标称型
效果演示¶
In [2]:
import kNN
获取数据集¶
In [3]:
group, label = kNN.createDataSet()
In [4]:
group
Out[4]:
In [5]:
label
Out[5]:
分类¶
In [6]:
kNN.classify0(inX = [0,0], dataSet = group, labels = label, k = 3)
Out[6]:
classify0函数¶
In [12]:
from numpy import *
import operator
from os import listdir
输入参数¶
In [8]:
# 测试数据
inX = [0, 0]
# 用于分类的数据集和标记
dataSet = group
labels = label
# k参数
k = 3
计算测试点到数据集各点的距离¶
差值、平方、求和、开根
In [10]:
# 获取数据集的行数
print(dataSet.shape)
dataSetSize = dataSet.shape[0]
np.tile函数说明¶
tile(A, reps)
按reps指定的大小扩展A数组
- A为一个np.array
- reps可以是单独一个数，也可以是一个元组
- tile将把A作为基本元素，按照reps指定的大小构造数组
- 举例：(a = np.array([[1,2], [3,4]]))
- np.tile(a, 2)
Output: array([[1,2,1,2], [3,4,3,4]]) -> 2x4 - np.tile(a, (2,1))
Output: array([[1,2], [3,4], [1,2], [3,4]]) -> 4x2
- np.tile(a, 2)
In [16]:
# 计算测试点到数据集各点在x、y轴上的差值
print("tile: ", tile(inX, (dataSetSize, 1)) )
print("dataSet: ", dataSet)
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
print("diffMat: ", diffMat)
In [21]:
# 平方：各元素分别平方
sqDiffMat = diffMat**2
# 求和：对第一维度求和
# 行是第零维度，列是第一维度
sqDistances = sqDiffMat.sum(axis=1)
# 开根
distances = sqDistances**0.5
np.argsort函数¶
a.argsort(axis = -1, kind = 'quicksort', order = None)
返回np.array的排序结果，这个结果以元素索引号的形式呈现（返回值类型为np.array）
In [26]:
# 获取距离的排序（argsort函数返回排序结果，但返回值为索引号）
sortedDistIndicies = distances.argsort()
print("distances: ", distances)
print("sortedDistIndicies: ", sortedDistIndicies)
统计距离最近的前k个数据集中标记出现的频次（k=3）¶
In [29]:
# 记录的字典
classCount = {}
# 统计前k个数据的标记出现频次
for i in range(k):
# 获取第i个数据的标记
voteIlabel = labels[sortedDistIndicies[i]]
# 计数
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
print("i:%d, distance:%f, voteIlabel:%s" % (i, distances[sortedDistIndicies[i]], voteIlabel))
print("classCount", classCount)
In [44]:
print("classCount.items(): ", classCount.items())
# 字典不可排序，需要转化为序列或迭代器
# 排序关键字：字典的值，也就是转化后的序列的第一项元素
# 反向：从高到低排序
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
print("sortedClassCount: ", sortedClassCount)
取得频次最大者作为预测的分类结果¶
In [41]:
sortedClassCount[0][0]
Out[41]:
In [ ]:
In [ ]:
使用Matplotlib绘制散点图¶
In [17]:
import kNN, matplotlib
import matplotlib.pyplot as plt
from numpy import *
In [11]:
datingDataMat, datingLabels = kNN.file2matrix('datingTestSet2.txt')
print("datingDataMat: ", datingDataMat)
print("datingLables[:20]: ", datingLabels[:20])
print("datingDataMat.shape: ", datingDataMat.shape)
print("len(datingLabels)", len(datingLabels))
用plt画散点图¶
创建图、添加子图、为子图添加数据和样式、显示图
第0列和第1列数据¶
明显划分出三个区域
In [33]:
# 创建一张图
fig = plt.figure()
# 添加一张子图，位置在1行1列的第一个位置（也即只有一张子图）
ax = fig.add_subplot(111) # 等价于fig.subplot(1,1,1)
# 为子图添加数据和样式
ax.scatter(datingDataMat[:,0], # x轴数据，取矩阵第0列
datingDataMat[:,1], # y轴数据，取矩阵第1列
c = array(datingLabels)) # 根据标记的数值设置数据颜色
plt.show()
第1列和第2列数据¶
区域重叠，划分不明显
In [30]:
# 创建一张图
fig = plt.figure()
# 添加一张子图，位置在1行1列的第一个位置（也即只有一张子图）
ax = fig.add_subplot(111) # 等价于fig.subplot(1,1,1)
# 为子图添加数据和样式
ax.scatter(datingDataMat[:,1], # x轴数据，取矩阵第1列
datingDataMat[:,2], # y轴数据，取矩阵第2列
c = array(datingLabels)) # 根据标记的数值设置数据颜色
plt.show()
第0列和第2列数据¶
有一定的区域划分，但重叠区域还是很多
In [31]:
# 创建一张图
fig = plt.figure()
# 添加一张子图，位置在1行1列的第一个位置（也即只有一张子图）
ax = fig.add_subplot(111) # 等价于fig.subplot(1,1,1)
# 为子图添加数据和样式
ax.scatter(datingDataMat[:,0], # x轴数据，取矩阵第0列
datingDataMat[:,2], # y轴数据，取矩阵第2列
c = array(datingLabels)) # 根据标记的数值设置数据颜色
plt.show()
In [ ]:
In [ ]:
数据归一化处理¶
newVal = ( oldVal - minVal ) / ( maxVal - minVal )
In [1]:
import kNN
from numpy import *
In [13]:
datingDataMat, datingLabels = kNN.file2matrix('datingTestSet2.txt')
print("datingDataMat: ", datingDataMat)
print("datingLables[:20]: ", datingLabels[:20])
print("datingDataMat.shape: ", datingDataMat.shape)
print("len(datingLabels)", len(datingLabels))
In [14]:
dataSet = datingDataMat
In [15]:
# 获取各列的最大最小值
# 即取得行即第零维的最大最小值
# 如果不指明维度，则表示取所有元素中的最大最小值
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
print("minVals: ", minVals)
print("maxVals: ", maxVals)
In [16]:
# 获取数据行数
m = dataSet.shape[0]
# 将（最大值 - 最小值） 和 最小值 向量扩展为m行
diffSet = tile( maxVals - minVals, (m, 1) )
minSet = tile( minVals, (m, 1) )
# 归一化
normDataSet = ( dataSet - minSet ) / diffSet
In [17]:
normDataSet
Out[17]:
In [ ]: